#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

//leetcode-10
//正则表达式匹配，动态规划，快
bool match(char *str, char *pattern)
{
    const int m = strlen(str), n = strlen(pattern);
    bool dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    for (int i = 0; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if ( j > 1 && pattern[j - 1] == '*')
            {
                if (i > 0 && (pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]))
                {
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = dp[i][j - 2];
                }
            }
            else
            {
                if (i > 0 && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]))
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }
    return dp[m][n];
}

//正则表达式匹配，递归，慢
bool isMatch(char *str, int i, char *pattern, int j)
{
    if (pattern[j] == '\0')
    {
        return str[i] == '\0';
    }
    if (pattern[j + 1] == '*')
    {
        if (str[i] != '\0' && (pattern[j] == '.' || pattern[j] == str[i]))
        {
            return isMatch(str, i, pattern, j + 2) || isMatch(str, i + 1, pattern, j);
        }
        else
        {
            return isMatch(str, i, pattern, j + 2);
        }
    }
    else if (pattern[j + 1] != '*')
    {
        if (str[i] != '\0' && (pattern[j] == '.' || pattern[j] == str[i]))
        {
            return isMatch(str, i + 1, pattern, j + 1);
        }
    }
    return false;
}

bool match(char *str, char *pattern)
{
    return isMatch(str, 0, pattern, 0);
}

void test()
{
}

int main()
{
    test();
    return 0;
}